题目分析
位运算的题目难度都不大,但是有一些技巧和陷阱需要小伙伴们在做题中发现,做完这个题目,希望小伙伴们可以去Leetcode官网做面试题05.06进行知识点巩固。
位运算
**负数右移,符号位不变,这是需要小伙伴们注意的,如果我们想让负数右移符号位补0,可以让结果异或0x8000000(1 << 31),或者让结果与(0x7fffffff)**。
本题中,我们从低位到高位统计连续的1出现的次数,如果某一位是0,则right统计右边1出现的个数,left统计左边1出现的个数。left + right + 1就是将该位改为1时连续的1出现的次数。然后再统计下一位,此时right = 0,left = right。
我写的版本是先找到最先出现的第一个0,统计右边1的个数记为right作为初始条件,然后开始统计left的个数。代码有些冗余,因此在下面提供一个其他人写的版本。
算法的**时间复杂度为$O(1)$,空间复杂度为$O(1)$**。
1 | #include<iostream> |
优化位运算
其实并没有优化时间复杂度和空间复杂度,但是美观了我们的代码,让我们的代码可读性大大提高了。
思想是:不管移位以后最高位补的是0还是1,我们只关心int的32位数据,因此使用for循环进行遍历,而且不需要找到第一个0产生的位置,统计右边1的个数赋值给right,将初始值right设0即可。
算法的**时间复杂度为$O(1)$,空间复杂度为$O(1)$**。
1 | #include<iostream> |
刷题总结
位运算是小伙伴们必须掌握的技能,这是我们软件程序员的基本知识,从计算机为什么要用二进制表示,到数值的二进制保存方法,这都是需要我们熟记的。